package com.gitee.ywj1352.算法.week04;

import java.util.HashSet;
import java.util.LinkedList;

public class 二分查找法 {

    /**
     *  // new PriorityQueue<>();
     *  // continue;
     *  // contains
     */



    int binarySearch(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1; // 注意

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target)
                return mid;
            else if (nums[mid] < target)
                left = mid + 1; // 注意
            else if (nums[mid] > target)
                right = mid - 1; // 注意
        }
        return -1;
    }


    static int left_bound(int[] nums, int target) {
        if (nums.length == 0) return -1;
        int left = 0;
        int right = nums.length; // 注意

        while (left < right) { // 注意
            int mid = (left + right) / 2;
            if (nums[mid] >= target) {
                right = mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            }
        }
        return left;
    }


    int right_bound(int[] nums, int target) {
        if (nums.length == 0) return -1;
        int left = 0, right = nums.length;

        while (left < right) {
            int mid = (left + right) / 2;
            if (nums[mid] <= target) {
                left = mid + 1; // 注意
            } else if (nums[mid] > target) {
                right = mid;
            }
        }
        return left - 1; // 注意
    }


    int lb(int[] nums, int target) {
        int l = 0, r = nums.length - 1, m;
        while (l < r) {
            m = (l + r) >> 1;
            if (nums[m] >= target) {
                r = m;
            } else if (nums[m] < target) {
                l = m + 1;
            }
        }
        return l;
    }

    int rb(int[] nums , int target){
        int l = 0, r = nums.length - 1, m;
        while (l< r){
            m = (l + r) >> 1;
            if(nums[m] <= target){
                l = m +1;
            }else if(nums[m] > target){
                r = m;
            }
        }
        return l-1;
    }

    public static int openLock(String[] deadends, String target) {
        LinkedList<String> queue = new LinkedList<String>();
        HashSet<String> visited = new HashSet<String>();
        int step = 0 ;
        HashSet<String> deadSet = new HashSet<>();
        for(int i = 0 ; i < deadends.length; i ++){
            deadSet.add(deadends[i]);
        }
        queue.addLast("0000");
        while(!queue.isEmpty()){
            int size = queue.size();
            for(int i = 0 ; i < size ; i++){
                String curr = queue.removeFirst();
                if(curr.equals(target)){
                    return step;
                }
                if(deadSet.contains(curr)){
                    continue;
                }
                for(int j = 0 ; j < 4; j++){
                    String up = up(curr,j);
                    if(!visited.contains(up)){
                        queue.addLast(up);
                        visited.add(up);
                        System.out.println(up);
                    }
                    String down = down(curr,j);
                    if( !visited.contains(down)){
                        queue.addLast(down);
                        visited.add(down);
                        System.out.println(down);
                    }
                }
            }
            step ++;
        }
        return -1;
    }
    private static String up(String num,int idx){
        char[] cArr = num.toCharArray();
        if(cArr[idx] < '9'){
            cArr[idx] = (char)(cArr[idx] +1);
            return new String(cArr);
        }
        return num;
    }
    private static String down(String num,int idx){
        char[] cArr = num.toCharArray();
        if(cArr[idx] > '0'){
            cArr[idx] = (char)(cArr[idx] -1);
            return new String(cArr);
        }
        return num;
    }

    public static void main(String[] args) {
        String[] nums = {"9999"};
        int i = openLock(nums, "0202");

        System.out.println(i);
        //Consume Cpu

    }




}
